package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * leetcode 40. 组合总和 II 组合问题的情况总和相当于
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/14 20:50
 */
public class E40 {
    /**
     * <h3>组合总和 II,用dfs递归加回溯剪枝解决</h3>
     * @param candidates 候选数组
     * @param target 目标值
     * @return 所有可能的结果
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // 先对数组进行排序，方便后续保证相同元素的有序选取
        List<List<Integer>> result = new ArrayList<>();
        dfs(0, candidates, result, target, new LinkedList<Integer>(), new boolean[candidates.length]);
        return result;
    }

    /**
     * 递归函数，dfs加递归
     * @param start 选取当前位置的数字时的起始数字
     * @param candidates 候选数组
     * @param result 结果集
     * @param target 目标值
     * @param currentCombine 当前组合
     * @param visited 标记数组所有元素的访问情况
     */
    private void dfs(int start,
                     int[] candidates,
                     List<List<Integer>> result,
                     int target,
                     LinkedList<Integer> currentCombine,
                     boolean[] visited) {
        // 递归终止条件：剩余目标值等于0，说明已经选取到了目标值，那么就加入到结果集中，然后返回
        if (target == 0){
            result.add(new ArrayList<>(currentCombine));
            return;
        }
        // 尝试当前位置的所有可能
        for (int i = start; i < candidates.length; i++){
            // 如果当前位置的当前遍历到的数字入选后，如果剩余目标值小于0了，那么后面的都没必要选入了（因为candidates数组排过序，升序），所以直接进行剪枝
            if (target - candidates[i] < 0) break;
            // 如果当前位置当前遍历到的数字和前一个数字一样，我们限定前一个数字访问过后才能访问当前数字，保证有序，进一步剪枝
            if (i > 0 && candidates[i] == candidates[i - 1] && !visited[i - 1]) continue;
            // 选取当前数字为当前位置
            currentCombine.push(candidates[i]);
            // 标记当前遍历到的数字已经访问过了
            visited[i] = true;
            // 递归选取下一个位置的数字
            dfs(i + 1, candidates, result, target - candidates[i], currentCombine, visited);
            // 回溯
            currentCombine.pop();
            visited[i] = false;
        }
    }
}
